剑指offer 37.数字在排序数组中出现的次数

剑指offer 37.数字在排序数组中出现的次数

题目

统计一个数字在排序数组中出现的次数。

思路

虽然递归已经是O(n)了，但是还要缩小，所以二分查找，找到前后的位置就行了。查找设k-0.5和k+0.5，反正都没有，所以能找到应该在的位置，然后减法就行。

代码

public int search(int[] array, double k) {
  int l = 0;
  int r = array.length - 1;
  int m = (r - l) / 2 + l;
  while (l <= r) {
    if (array[m] < k) {
      l = m + 1;
    } else {
      r = m - 1;
    }
    m = (r - l) / 2 + l;
  }
  return l;
}

public int GetNumberOfK(int[] array, int k) {
  int start = search(array, k - 0.5);
  int end = search(array, k + 0.5);
  return end - start;
}